import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/27 21:16
 * @description 01 字典树
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 4 , 2, 7};
        solution.countPairs(nums, 2, 6);
    }
    static int highBit = 14;
    Trie root = new Trie();
    public int countPairs(int[] nums, int low, int high) {
        int ans = 0;
        for (int num : nums) {
            ans += smaller(num, high + 1) - smaller(num, low);
            insert(num);
        }
        return ans;
    }
    public void insert(int val) {
        Trie node = root;
        for(int i = highBit; i >= 0; i--) {
            // 右移i位
            int bit = (val >> i) & 1;

            if (node.children[bit] == null) {
                node.children[bit] = new Trie();
            }
            node = node.children[bit];
            node.count++;
        }
    }

    /**
     * 小于 limit的 数的个数
     * @param val
     * @param limit
     * @return
     */
    public int smaller(int val, int limit) {
        int count = 0;
        Trie node = root;
        for(int i = highBit; i >= 0; i--) {
            if (node == null) {
                return count;
            }
            int bit = (val >> i) & 1, limitBit = (limit >> i) & 1;
            if (limitBit == 1) {
                // bitA为0， 那么bitB = 0, 左走必成，0 ^ 0 = 0 < 1, 再试试右
                // bitA为1，那么bitB = 1, 右走必成，1 ^ 1 = 0 < 1, 再试试左
                if (node.children[bit] != null) {
                    count += node.children[bit].count;
                }
                // 取相异的节点异或为1，
                node = node.children[bit ^ 1];
            }else {
                // limitBit = 0, 那么要使 <=, 那么num的bit必须相等，不存在比0小的数，直接下一个节点
                node = node.children[bit];
            }
        }
        return count;
    }
}
class Trie{

    Trie[] children = new Trie[2];
    int count = 0;
}
